package com.aqie.arithmetic.datastructure;

import edu.princeton.cs.algs4.StdOut;

import java.util.Iterator;

/**
 * 可伸缩容量LIFO 栈， 支持迭代
 * 对象游离： 被弹出的对象引用依然存在数组中，元素永远不会被访问,数组的引用使其不被Java回收
 */
public class ScalableCapacityStack<T> {
    private T[] a;
    private int N;

    public ScalableCapacityStack(int cap) {
        a = (T[])new Object[cap];
    }

    public boolean isEmpty(){
        return N == 0;
    }
    public int size(){
        return N;
    }

    private void resize(int max){
        // 将大小为N <= max 的栈移动到新的 max数组中
        T[] tmp = (T[])new Object[max];
        for (int i = 0; i < N; i++){
          tmp[i] = a[i];
        }
        a = tmp;
    }

    public void push(T item){
        // 将元素压入栈
        if (N == a.length) resize(2 * a.length);
        a[N++] = item;
    }

    public T pop(){
        // 从栈顶删除元素
        T item = a[--N];
        // 避免对象游离
        a[N] = null;
        if (N > 0 && N == a.length / 4) resize(a.length / 2);
        return item;
    }

    public Iterator<T> iterator(){
        return new ReverseArrayIterator();
    }

    private class ReverseArrayIterator implements  Iterator<T>{
        private int i = N;

        @Override
        public boolean hasNext() {
            return i > 0;
        }

        @Override
        public T next() {
            return a[--i];
        }

        @Override
        public void remove(){
          // do nothing
        }
    }

    public static void main(String[] args) {
        ScalableCapacityStack<Integer> stack = new ScalableCapacityStack<>(2);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        // 迭代
        Iterator<Integer> iterator = stack.iterator();
        while (iterator.hasNext()){
            StdOut.println(iterator.next());
        }
    }

}
